package com.desin.modle.datastruct.tree;


import javax.swing.tree.TreeNode;
import java.util.*;

public class BinarySearchTree {
    private Node tree;

    public Node find(int data){
        Node p = tree;//当前节点
        while (p!=null){
            if(data>p.data){
                p=p.right;
            }else if(data<p.data){
                p=p.left;
            }else {
                return p;
            }
        }
        return null;
    }

    public void insert(int data){
        if(tree == null){
            tree = new Node(data);
            return;
        }

        Node q = new Node(data);//要插入的叶子节点
        Node p = tree;//要插入叶子节点的父节点
        while (p!=null){
            if(data>p.data){
                if(p.right==null){
                    p.right = q;
                }
                p = p.right;
            }else if(data<p.data){
                if(p.left==null){
                    p.left = q;
                }
                p = p.left;
            }
        }
    }

    public void delete(int data){
        if(tree == null){
            return;
        }
        Node p = tree;//指向要删除的节点
        Node pp = null;//指向其父节点
        while (p!=null&&p.data!=data){
            pp=p;
            if(data>p.data){
                p = p.right;
            }else if(data<p.data){
                p = p.left;
            }
        }
        if(p==null){
            return;
        }
        //删除的节点有两个子节点
        if (p.left!=null&&p.right!=null){
            Node minP = p.right;
            Node minPP = p;
            while (minP.left!=null){
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;
            pp = minPP;
        }
        //删除的节点没有子节点或者只有一个子节点
        Node child;
        if(p.left!=null){
            child = p.left;
        }else if(p.right!=null){
            child = p.right;
        }else{
            child = null;
        }

        if(pp==null){//如果要删除的节点是根节点
            tree = child;
            return;
        }
        if(pp.left == p){
          pp.left = child;
        }else if(pp.right==p){
            pp.right = child;
        }
    }

    public Node findMax(){
        if(tree==null){
            return null;
        }
        Node p = tree;
        while (p!=null){
            if(p.right==null){
                return p;
            }
            p = p.right;
        }
        return p;
    }

    public Node findMin(){
        if(tree==null){
            return null;
        }
        Node p = tree;
        while (p!=null){
            if(p.left==null){
                return p;
            }
            p = p.left;
        }
        return p;
    }

//    public static void main(String[] args) throws ClassNotFoundException {
//        Class<?> aClass = Class.forName("java.lang.Math");
//        ClassLoader classLoader = aClass.getClassLoader();
//        System.out.println("classLoader = "+classLoader);
//    }

    class Node{
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode temp = queue.poll();
            list.add(temp.val);
            if(temp.left!=null){
                queue.offer(temp.left);
            }
            if(temp.right!=null){
                queue.offer(temp.right);
            }
        }
        int[] res = new int[list.size()];
        int i=0;
        for(Integer num:list){
            res[i++]=num;
        }
        return res;
    }

    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> list1 = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode temp = queue.poll();
                list1.add(temp.val);
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
            list.add(list1);
        }
        return list;
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list1 = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode temp = queue.poll();
                list1.add(temp.val);
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
            if(!flag){
                Collections.reverse(list1);
            }
            flag=!flag;
            list.add(list1);
        }

        return list;
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A!=null&&B!=null)&&(isSubStructureHelper(A,B)||isSubStructureHelper(A.left,B)||isSubStructureHelper(A.right,B));
    }

    private boolean isSubStructureHelper(TreeNode a, TreeNode b) {
        if(b==null){
            return true;
        }
        if(a==null||a.val!=b.val){
            return false;
        }
        return isSubStructureHelper(a.left,b.left)&&isSubStructureHelper(a.right,b.right);
    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Deque<Integer> queue = new LinkedList<>();
        dfs(root,0,target,res,queue);
        return res;
    }

    private void dfs(TreeNode root, int start, int target, List<List<Integer>> res,Deque queue) {
        if(root==null){
            return ;
        }
        queue.offer(root.val);
        if(start+root.val==target&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(queue));
        }
        dfs(root.left, start + root.val, target, res, queue);
        dfs(root.right, start + root.val, target, res, queue);
        queue.removeLast();
    }
    int tempK;
    int res;
    public int kthLargest(TreeNode root, int k) {
        this.tempK = k;
        dfsTemp(root);
        return res;
    }

    private void dfsTemp(TreeNode root) {
        if(root==null){
            return;
        }
        dfsTemp(root.right);
        if(tempK==0){
            return;
        }
        if(--tempK==0){
            res=root.val;
        }
        dfsTemp(root.left);
    }

    public Node treeToDoublyList(Node root) {
        if(root==null){
            return root;
        }
        if(root.left==null&&root.right==null){
            root.left=root;
            root.right=root;
            return root;
        }
        List<Node> list = new ArrayList<>();
        dfs(root,list);
        Node[] array = list.toArray(new Node[list.size()]);
        for(int i=0;i<array.length;i++){
            if(i==0){
                array[i].left=array[array.length-1];
                array[i].right=array[i+1];
            }else if(i==array.length-1){
                array[i].left=array[i-1];
                array[i].right=array[0];
            }else{
                array[i].left=array[i-1];
                array[i].right=array[i+1];
            }
        }
        return array[0];
    }

    private void dfs(Node root, List<Node> list) {
        if(root==null){
            return;
        }
        dfs(root.left,list);
        list.add(root);
        dfs(root.right,list);
    }

    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Integer.max(maxDepth(root.left),maxDepth(root.right))+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length==0){
            return null;
        }
        Map<Integer,Integer> map = new HashMap<>();
        int n = preorder.length;
        for(int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        return buildTreeHelper(preorder,inorder,map,0,n-1,0,n-1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, Map<Integer, Integer> map, int preLeft, int preRight, int inLeft, int inRight) {
        if(preLeft>preRight){
            return null;
        }
        int inRoot = map.get(preorder[preLeft]);
        int nextPreSize = inRoot-inLeft;
        TreeNode root = new TreeNode(preorder[preLeft]);
        root.left=buildTreeHelper(preorder,inorder,map,preLeft+1,preLeft+nextPreSize,inLeft,inRoot-1);
        root.right=buildTreeHelper(preorder,inorder,map,preLeft+nextPreSize+1,preRight,inRoot+1,inRight);
        return root;
    }

    public List<List<Integer>> levelTree(TreeNode node){
        List<List<Integer>> list = new ArrayList<>();
        if(node==null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tempList = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode temp = queue.poll();
                tempList.add(temp.val);
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
            list.add(tempList);
        }
        return list;
    }

    public void preTree(TreeNode tree){
        if(tree==null){
            return;
        }
        System.err.println(tree.val);
        preTree(tree.left);
        preTree(tree.right);
    }

    public List<Integer> leftTree(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                list.add(root.val);
                stack.push(root);
                root=root.left;
            }else{
                TreeNode temp = stack.pop();
                root=temp.right;
            }
        }
        return list;
    }

    public void inTree(TreeNode tree){
        if(tree==null){
            return;
        }
        inTree(tree.left);
        System.err.println(tree.val);
        inTree(tree.right);
    }

    public List<Integer> midTree(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                TreeNode temp = stack.pop();
                list.add(temp.val);
                root=temp.right;
            }
        }
        return list;
    }

    public void afterTree(TreeNode tree){
        if(tree==null){
            return;
        }
        afterTree(tree.left);
        afterTree(tree.right);
        System.err.println(tree.val);
    }

    public List<TreeNode> generateTree(int n){
        if(n<=0){
            return new ArrayList<TreeNode>();
        }
        return generateTreeHelper(1,n);
    }

    public List<TreeNode> generateTreeHelper(int start,int end){
        List<TreeNode> list = new ArrayList<>();
        if(start>end){
            return list;
        }
        for(int i=start;i<=end;i++){
            List<TreeNode> leftList = generateTreeHelper(start,i-1);
            List<TreeNode> rightList = generateTreeHelper(i+1,end);
            for(TreeNode left:leftList){
                for(TreeNode right:rightList){
                    TreeNode root = new TreeNode(i);
                    root.left=left;
                    root.right=right;
                    list.add(root);
                }
            }
        }
        return list;
    }

    public boolean isMirrorTree(TreeNode root){
        if(root==null){
            return true;
        }
        return isMirrorTreeHelper(root.left,root.right);
    }

    private boolean isMirrorTreeHelper(TreeNode left, TreeNode right) {
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        if(left.val!=right.val){
            return false;
        }
        return isMirrorTreeHelper(left.left,right.right)&&isMirrorTreeHelper(left.right,right.left);
    }

    public boolean isBalancedNew(TreeNode root){
        if(root==null){
            return true;
        }
        int leftHeight = isBalancedHelper(root.left);
        int rightHeight = isBalancedHelper(root.right);
        return (Math.abs(leftHeight-rightHeight)<=1)&&isBalancedNew(root.left)&&isBalancedNew(root.right);
    }

    private int isBalancedHelper(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(isBalancedHelper(root.left)+1,isBalancedHelper(root.right)+1);
    }
    class ComplateHelper {
        TreeNode node;
        int val;
        public ComplateHelper(TreeNode node,int val){
            this.node=node;
            this.val=val;
        }
    }
    public boolean isComplate(TreeNode root){
        if(root==null){
            return false;
        }
        List<ComplateHelper> list = new ArrayList<>();
        list.add(new ComplateHelper(root,1));
        int i=0;
        for(;i<list.size();i++){
            ComplateHelper temp = list.get(i);
            if(temp!=null){
                list.add(new ComplateHelper(temp.node.left,temp.val*2));
                list.add(new ComplateHelper(temp.node.right,temp.val*2+1));
            }
        }
        return list.get(i-1).val==list.size();
    }

    public List<List<Integer>> pathSumNew(TreeNode root,int target){
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Deque<Integer> queue = new LinkedList<>();
        pathSumHelperNew(root,0,target,queue,res);
        return res;
    }

    private void pathSumHelperNew(TreeNode root, int start, int target, Deque<Integer> queue, List<List<Integer>> res) {
        if(root==null){
            return;
        }
        queue.offer(root.val);
        if(start+root.val==target&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(queue));
        }
        pathSumHelperNew(root.left,start+root.val,target,queue,res);
        pathSumHelperNew(root.right,start+root.val,target,queue,res);
        queue.removeLast();
    }
}
